<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3092：[FDU2012校赛] A Famous King’s Trip </title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[FDU2012校赛] A Famous King’s Trip </a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[FDU2012校赛] A Famous King’s Trip </span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [FDU2012校赛] A Famous King’s Trip                 </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="margin: 11.75pt -1.5pt 0pt 0cm; line-height: 17.25pt" align="left"></div>
<div style="margin: 10.5pt 19.85pt 0pt 0cm; line-height: 12.85pt"><span style="font-size: medium"><span style="color: black">Mr. B is the chief engineer in the Kingdom of FDUCS. Recently, the King asks Mr. B to develop a new plan of the road network in the country, since the existing one is so outdated that traffic jam often occurs. Unfortunately, Mr. B is now busy preparing for the ICPC World Finals. Therefore, He asks his friends Mr. G and Mr. M to help him finish that work. When Mr. B gets the solution from his friends, he realizes some problems: Mr. B forgot to specify the budget plan to Mr. G and Mr. M, thus the new solution contains too many new roads which the government cannot afford. After a precise calculation, Mr. B finds that he only need to delete exactly two roads in term of the financial facts (Of course, Mr. B will not delete more than two roads because he wants people in his country to have a convenient traffic). </span></span></div>
<div style="margin: 10.5pt 19.9pt 0pt 0cm; line-height: 12.75pt"><span style="font-size: medium"><span style="color: black">Can Mr. B delete two roads arbitrarily? The answer is negative. The King would like to take a travel on the new road system to review Mr. B's work. However, the King is so busy that he does not want to take travel with redundancy. That is, the King wants Mr. B to design a road system so that he can travel from the palace (in one city), pass each road exactly once, and then return to the palace. Moreover, during his travelling, the king must visit each city at least once. </span></span></div>
<div style="margin: 10.5pt 20.05pt 0pt 0cm; line-height: 12pt"><span style="font-size: medium"><span style="color: black">Mr. B feels hard to satisfy the King&rsquo;s demand by deleting two roads from the original design. As an ICPC candidate with unlimited potential, can you help him? </span></span></div></p><hr/><h3>输入格式</h3><p><div style="margin: 0cm 19.85pt 0pt 0cm; line-height: 12.65pt"><span style="font-size: medium"><span style="color: black">For each test case, the first line contains two integers, n and m (1 &lt;= n, m &lt;= 200,000), indicating the number of cities in the Kingdom and the roads in Mr. B's original plan. Following this are m lines, each contains a pair of integers a and b, denoting a bidirectional road between city a and city b (1 &lt;= a, b &lt;= n and a != b), the number of cities are counted from 1. No two roads connect the same pair of cities. </span></span></div></p><hr/><h3>输出格式</h3><p><div style="margin: 10.5pt -1.1pt 0pt 0cm; line-height: 13.5pt" align="left">&nbsp;</div>
<div style="margin: 0cm 19.8pt 0pt 0cm; line-height: 12.75pt"><span style="font-size: medium"><span style="color: black">For each test case, if Mr. B can satisfy the King&rsquo;s requirement, then output &ldquo;YES&rdquo; in the first line, otherwise output &ldquo;NO&rdquo; (quotes for clarifying). If the answer is &ldquo;YES&rdquo;, output two integers X and Y (X &lt; Y) in the following line, specifying the two roads that Mr. B should delete from the original design. X and Y are the indexes of roads in the input, counting from 1. If there are more than one possible answer, output the one that makes the pair of (X, Y) lexicographically smallest. </span></span></div></p><hr/><h3>样例输入</h3><pre>4  6
1  2
1  3
1  4
2  3
2  4
3  4
</pre><hr/><h3>样例输出</h3><pre>Case 1: YES 
1  6
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3092" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3092" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>